백준 7453번

오늘 풀어본 문제는 백준의 7453번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

정수로 이루어진 크기가 같은 배열 $A$, $B$, $C$, $D$ 가 있다.

$A[a]$, $B[b]$, $C[c]$, $D[d]$ 의 합이 $0$ 인 $(a,\ b,\ c,\ d)$ 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 $n$ $(1 \le n \le 4000)$ 이 주어진다. 다음 $n$ 개 줄에는 $A,\ B,\ C,\ D$ 에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 $2^{28}$ 이다.

출력

합이 $0$ 이 되는 쌍의 개수를 출력한다.

풀이과정

1번째 시도

예전에 비슷한 문제를 본적이 있던 것 같았고, 이번에도 그 문제에 사용했던 풀이법을 적용해보기로 했다.

우선 $A$ 와 $B$ 배열의 모든 원소를 순회하며 두 원소의 합을 std::unordered_map에 저장하는데, 원소의 조합은 달라도 합이 같을 수 있기 때문에 등장 횟수를 함께 저장하도록 하였다.

$A$ 와 $B$ 에 대한 순회가 모두 끝나면, 이번에는 $C$ 와 $D$ 를 순회하며 두 원소의 합과 부호가 반대인 수가 해시 테이블에 있다면, 등장 횟수를 최종 결과에 더해주는 방식으로 총 조합의 개수를 알아낼 수 있을 것이라고 생각하였다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> A(n), B(n), C(n), D(n);
    
    for (int i=0; i<n; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    sort(D.begin(), D.end());
    
    unordered_map<int, int> sumCounts;
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int sum = A[i] + B[j];
            
            if (sumCounts.find(sum) == sumCounts.end()) {
                sumCounts[sum] = 0;
            }
            
            sumCounts[sum]++;
        }
    }
    
    int result = 0;
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int sum = C[i] + D[j];
            
            if (sumCounts.find(0 - sum) != sumCounts.end()) {
                result += sumCounts[0 - sum];
            }
        }
    }
    
    cout << result;
    
    return 0;
}

실행 결과 ‘시간 초과’ 가 떴다.

2번째 시도

첫 번째 제출의 코드에서 배열을 정렬하는 부분이 있는데, 이는 전혀 필요없는 부분이었다. 혹시 이 부분이 쓸데없이 시간을 낭비해서 시간 초과가 발생한 것인가 싶어 지우고 다시 제출해보았다.

코드는 다음과 같이 수정하였다.

#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> A(n), B(n), C(n), D(n);
    
    for (int i=0; i<n; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    
    unordered_map<int, int> sumCounts;
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int sum = A[i] + B[j];
            
            if (sumCounts.find(sum) == sumCounts.end()) {
                sumCounts[sum] = 0;
            }
            
            sumCounts[sum]++;
        }
    }
    
    int result = 0;
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int sum = C[i] + D[j];
            
            if (sumCounts.find(0 - sum) != sumCounts.end()) {
                result += sumCounts[0 - sum];
            }
        }
    }
    
    cout << result;
    
    return 0;
}

실행 결과 ‘시간 초과’ 가 떴다.

3번째 시도

정렬 코드가 문제가 된 것은 아니었고, 아무래도 해시 테이블 자체를 사용하는데에 뭔가 문제가 있었던 것 같았다. 질문 게시판을 둘러봐도 해시 테이블을 사용했으나 시간 초과가 발생한 경우가 있는 것 같았다.

듣기로는 PS의 세계에서는 해시 테이블을 이용한 풀이를 저격하는 음해 세력(?) 이 있다고 들었다. 혹시 이 문제도 그런 경우인가 싶어 예전에 만들어두었던 실행 시간에 따라 해시 방식이 달라지는 해시 함수를 사용하려고 했지만, 깃헙에 업로드 해놓지 않았다!

하는 수 없이 다른 사람이 만들어둔 해시 함수를 사용하기로 했다.

코드는 다음과 같이 수정하였다.

#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> A(n), B(n), C(n), D(n);
    
    for (int i=0; i<n; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    
    unordered_map<int, int, custom_hash> sumCounts;
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int sum = A[i] + B[j];
            
            if (sumCounts.find(sum) == sumCounts.end()) {
                sumCounts[sum] = 0;
            }
            
            sumCounts[sum]++;
        }
    }
    
    int result = 0;
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int sum = C[i] + D[j];
            
            if (sumCounts.find(0 - sum) != sumCounts.end()) {
                result += sumCounts[0 - sum];
            }
        }
    }
    
    cout << result;
    
    return 0;
}

실행 결과 ‘시간 초과’ 가 떴다.

4번째 시도

이렇게까지 했는데도 저격을 하는 건 불가능해보였다. 질문 게시판을 좀 더 둘러본 결과, std::unordered_map 의 동작의 상수가 커서 문제가 될 수 있다는 내용을 발견하였고, 다른 대체제가 있다는 것을 알게되었다!

gcc 컴파일러는 내가 기존에 알던 C++ STL과는 또 다른 해시 테이블 자료 구조를 지원했던 것이다. 그 이름은 gp_hash_table 로, 이름부터 해시 테이블이었다. std::unordered_map 대신 이걸 써보기로 했다.

코드는 다음과 같이 수정하였다.

#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

struct time_based_hash {
	[[gnu::const]] static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	[[gnu::const]] size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x ^ FIXED_RANDOM);
	}
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> A(n), B(n), C(n), D(n);
    
    for (int i=0; i<n; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    
    __gnu_pbds::gp_hash_table<int, int, time_based_hash> sumCounts;
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int sum = A[i] + B[j];
            
            if (sumCounts.find(sum) == sumCounts.end()) {
                sumCounts[sum] = 0;
            }
            
            sumCounts[sum]++;
        }
    }
    
    int result = 0;
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int sum = C[i] + D[j];
            
            if (sumCounts.find(0 - sum) != sumCounts.end()) {
                result += sumCounts[0 - sum];
            }
        }
    }
    
    cout << result;
    
    return 0;
}

실행 결과 ‘컴파일 에러’ 가 떴다.

5번째 시도

컴파일 에러가 뜬 원인은, 새로운 자료 구조를 사용하기 위한 헤더 파일을 포함하는 것을 깜빡했던 것이었다.

코드는 다음과 같이 수정하였다.

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include <unordered_map>

#include<ext/pb_ds/assoc_container.hpp>

using namespace std;

struct time_based_hash {
	[[gnu::const]] static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	[[gnu::const]] size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x ^ FIXED_RANDOM);
	}
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> A(n), B(n), C(n), D(n);
    
    for (int i=0; i<n; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    
    __gnu_pbds::gp_hash_table<int, int, time_based_hash> sumCounts;
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int sum = A[i] + B[j];
            
            if (sumCounts.find(sum) == sumCounts.end()) {
                sumCounts[sum] = 0;
            }
            
            sumCounts[sum]++;
        }
    }
    
    int result = 0;
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int sum = C[i] + D[j];
            
            if (sumCounts.find(0 - sum) != sumCounts.end()) {
                result += sumCounts[0 - sum];
            }
        }
    }
    
    cout << result;
    
    return 0;
}

실행 결과 ‘틀렸습니다’ 가 떴다.

6번째 시도

이전 제출이 틀렸던 원인은 가능한 경우의 수가 int의 범위를 넘어갈 수 있다는 것을 놓쳤기 때문이었다. result 의 자료형을 long long int 로 바꿔주면 해결될 것이라고 생각했다.

코드는 다음과 같이 수정하였다.

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include <unordered_map>

#include<ext/pb_ds/assoc_container.hpp>

using namespace std;

struct time_based_hash {
	[[gnu::const]] static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	[[gnu::const]] size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x ^ FIXED_RANDOM);
	}
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> A(n), B(n), C(n), D(n);
    
    for (int i=0; i<n; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    
    __gnu_pbds::gp_hash_table<int, int, time_based_hash> sumCounts;
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int sum = A[i] + B[j];
            
            if (sumCounts.find(sum) == sumCounts.end()) {
                sumCounts[sum] = 0;
            }
            
            sumCounts[sum]++;
        }
    }
    
    long long int result = 0;
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            int sum = C[i] + D[j];
            
            if (sumCounts.find(0 - sum) != sumCounts.end()) {
                result += sumCounts[0 - sum];
            }
        }
    }
    
    cout << result;
    
    return 0;
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

이 문제를 풀면서 gp_hash_table 이라는 새로운 흑마술의 세계에 입문하게 되었다! C++ 표준은 아닌 것 같지만, 백준에서 잘 작동하니 괜찮지 않겠는가? 앞으로 해시 테이블은 이걸로 써야겠다. 이거 말고도 gcc 확장 기능이 있는지 더 알아봐도 좋을 것 같다.

그리고 솔브드 업데이트로 인해 뺏겼던 CLASS 5 은장을 다시 되찾는데 성공하였다!

CLASS 5 Essential

이제 남은 건 CLASS 5 금장뿐이다. 후딱 해치워버리고 CLASS 6을 달성하러 가고싶다!

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/7453

← Previous Post Next Post →